package sort;

import java.util.Arrays;

/**
 * @Classname ShellSort
 * @Author happytaohaha
 * @Date 2020/2/29
 * @Description 希尔排序
 * 复杂度是O(n(logN)^2) 或O(n^1.5) 稍大于归并排序， 但是归并排序使用了额外的空间， 快速排序虽然也是O(nlogN) 但是快排不够稳定,可能复杂度更大。
 * 最主要理解如何进行往回进行插入排序。
 * 最好的分法是 len/3+1  然后往下降 每次都是 increment/3+1
 */
public class ShellSort {

    public static int[] shellSort(int[] array) {
        int len = array.length;
        int increment = len;
        while (increment > 1) {
            //increment > 1  1. 是为了防止len<0 2. 是为了防止increment / 3 + 1;  最后结果为1  因为最后一次必为 1 进行最后一次循环
            increment = increment / 3 + 1;
            for (int i = increment; i < len; i++) {
                int j = i - increment;
                int value = array[i];
                //只找大于且下表小于value的值，进行插入排序的交换
                for (; j >= 0 && array[j] > value; j -= increment) {
                    array[j + increment] = array[j];
                }
                //找到小下表但值比value大的数，然后将value 插入到 j + increment 的位置。
                array[j + increment] = value;

            }

        }

        return array;
    }


    public static void main(String[] args) {
        System.out.println(Arrays.toString(shellSort(new int[]{6, 5, 4, 3, 2, 1})));
    }
}
